# check out this stuff
import difflib


def hamming(a, b):
    """ Returns the hamming ditance between two strings."""
    assert len(a) == len(b)
    return sum(ch1 != ch2 for ch1, ch2 in zip(a, b))

def levenshtein(a, b): #stolen from m.l. hetland
    """ Returns the levenshtein distance between two strings."""
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a, b = b, a
        n, m = m, n
    current = xrange(n + 1)
    for i in xrange(1, m + 1):
        previous, current = current, [i] + [0] * m
        for j in xrange(1, n+1):
            add, delete = previous[j] + 1, current[j-1] + 1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change += 1
            current[j] = min(add, delete, change)
    return current[n]

def relative(a, b, distance=levenshtein):
    """ Computes a relative distance between two strings.
    Its in the range (0-1] where 1 means total equality.
    """
    d = distance(a, b)
    longer = float(max((len(a), len(b))))
    shorter = float(min((len(a), len(b))))    
    r = ((longer - d) / longer) * (shorter / longer)
    return r
